package 剑指Offer.中等;

import Entity.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
 * <p>
 * 叶子节点 是指没有子节点的节点。
 * 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
 * 输出：[[5,4,11,2],[5,8,4,5]]
 * 示例 2：
 * <p>
 * <p>
 * <p>
 * 输入：root = [1,2,3], targetSum = 5
 * 输出：[]
 * 示例 3：
 * <p>
 * 输入：root = [1,2], targetSum = 0
 * 输出：[]
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author caihe
 * @date 2022/9/23 10:16
 */
public class _34二叉树中和为某一值的路径 {

    List<List<Integer>> resList = new LinkedList<>();
    // 临时队列：用来维护根节点到叶子节点的路径 
    Deque<Integer> queue = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return resList;
    }

    public void dfs(TreeNode root, int target) {
        if (root == null) {
            return;
        }
        // 当前节点的值放入临时队列中
        int val = root.val;
        queue.offerLast(val);
        // 目标值减当前节点值
        target -= val;
        // 当前节点为叶子节点 及 目标值最后为0时
        if (root.left == null && root.right == null && target == 0) {
            // 将临时队列最终的值放入结果集中
            resList.add(new LinkedList<>(queue));
        }
        dfs(root.left, target);
        dfs(root.right, target);
        // 移除临时队列中的最后的节点
        queue.removeLast();
    }

}
